package dp.二维数组;


/**
 * https://leetcode.cn/problems/unique-paths/
 *
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493732&idx=1&sn=3b606ee840ea4974a7f600a1043806f3&chksm=9bd4166caca39f7a7e566d89710b04b4a30d1b0d3182f9d01161e1fb737eceeb90d72a62cc46&scene=178&cur_album_id=2165181514903355392#rd
 */
public class _62_不同路径 {

    public static void main(String[] args) {
        int m = 3;
        int n = 7;
        _62_不同路径 _62_不同路径 = new _62_不同路径();
        int result = _62_不同路径.uniquePaths(m,n);
        System.out.println(result);
    }


    int[][] meno;

    public int uniquePaths(int m, int n) {
        meno = new int[m][n];
        return dp(m - 1, n - 1);
    }

    private int dp(int m, int n) {
        if (m == 0 || n == 0) return 1;
        if (m < 0 || n < 0) return 0;

        if (meno[m][n] != 0) return meno[m][n];

        meno[m][n] = dp(m - 1, n) + dp(m, n - 1);

        return meno[m][n];
    }
}
